package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(numSquares(13))
}

func numSquares(n int) int {
	dp := []int{0}
	for i := 1; i <= n; i++ {
		dp = append(dp, math.MaxInt)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j*j <= i; j++ {
			dp[i] = min279(dp[i-j*j]+1, dp[i])
		}
	}
	return dp[n]
}

func min279(a, b int) int {
	if a < b {
		return a
	}
	return b
}
